<html>
  <head>
	  <meta http-equiv="content-type" content="text/html; charset=utf-8" />
    <title>i5ting_ztree_toc:线性表（三）</title>
		<link href="toc/style/github-bf51422f4bb36427d391e4b75a1daa083c2d840e.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/style/github2-d731afd4f624c99a4b19ad69f3083cd6d02b81d5.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/css/zTreeStyle/zTreeStyle.css" media="all" rel="stylesheet" type="text/css"/>
	  <style>
		pre {
		    counter-reset: line-numbering;
		    border: solid 1px #d9d9d9;
		    border-radius: 0;
		    background: #fff;
		    padding: 0;
		    line-height: 23px;
		    margin-bottom: 30px;
		    white-space: pre;
		    overflow-x: auto;
		    word-break: inherit;
		    word-wrap: inherit;
		}

		pre a::before {
		  content: counter(line-numbering);
		  counter-increment: line-numbering;
		  padding-right: 1em; /* space after numbers */
		  width: 25px;
		  text-align: right;
		  opacity: 0.7;
		  display: inline-block;
		  color: #aaa;
		  background: #eee;
		  margin-right: 16px;
		  padding: 2px 10px;
		  font-size: 13px;
		  -webkit-touch-callout: none;
		  -webkit-user-select: none;
		  -khtml-user-select: none;
		  -moz-user-select: none;
		  -ms-user-select: none;
		  user-select: none;
		}

		pre a:first-of-type::before {
		  padding-top: 10px;
		}

		pre a:last-of-type::before {
		  padding-bottom: 10px;
		}

		pre a:only-of-type::before {
		  padding: 10px;
		}

		.highlight { background-color: #ffffcc } /* RIGHT */
		</style>
  </head>
  <body>
	  <div>
				<div style='width:25%;'>
						<ul id="tree" class="ztree" style='width:100%'>

						</ul>
				</div>
        <div id='readme' style='width:70%;margin-left:20%;'>
          	<article class='markdown-body'>
            	<h1 id="-">线性表（三）</h1>
<h3 id="15-"><a href="https://leetcode-cn.com/problems/3sum/">15. 三数之和</a></h3>
<p>给你一个包含 <code>n</code> 个整数的数组 <code>nums</code>，判断 <code>nums</code> 中是否存在三个元素 <em>a，b，c ，</em>使得 <em>a + b + c =</em> 0 ？请你找出所有和为 <code>0</code> 且不重复的三元组。</p>
<p><strong>注意：</strong>答案中不可以包含重复的三元组。</p>
<h4 id="-1-"><strong>示例 1：</strong></h4>
<pre><code>输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
</code></pre><h4 id="-2-"><strong>示例 2：</strong></h4>
<pre><code>输入：nums = []
输出：[]
</code></pre><h4 id="-3-"><strong>示例 3：</strong></h4>
<pre><code>输入：nums = [0]
输出：[]
</code></pre><hr>
<h4 id="-">解法</h4>
<p>思路：先排序后三指针。</p>
<p>for循环，当前循环到值为固定指针，然后确定两个动态指针。</p>
<pre><code class="lang-java">class Solution {
    public List&lt;List&lt;Integer&gt;&gt; threeSum(int[] nums) {
        Arrays.sort(nums);
        List&lt;Integer&gt; list = null;
        List&lt;List&lt;Integer&gt;&gt; lists = new LinkedList&lt;&gt;();

        //for循环，nums[i]为固定指针
        for (int i = 0; i &lt; nums.length; i++) {
            // 说明最小的数，都大于0了，没必要再继续了；
            int curr = nums[i];
            if(curr &gt; 0) return lists;

            // 与上一位相等直接continue
            if(i &gt; 0 &amp;&amp; nums[i] == nums[i-1]){
                continue;
            }

            //确定左右两个指针
            int L = i+1;
            int R = nums.length-1;
            while (L &lt; R){
                //当前和
                int total = curr + nums[L] + nums[R];
                if(total == 0){
                    list = new LinkedList&lt;&gt;();
                    list.add(curr); list.add(nums[L]); list.add(nums[R]);
                    lists.add(list);
                    //L与下一位比较
                    while(L &lt; R &amp;&amp; nums[L] == nums[L+1]){
                        ++L;
                    }
                    //R与上一位比较
                    while (L &lt; R &amp;&amp; nums[R] == nums[R-1]){
                        --R;
                    }
                    ++L;
                    --R;
                }
                if(total &lt; 0){
                    ++L;
                }
                else if(total &gt; 0){
                    --R;
                }
            }
        }
        return lists;
    }
}
</code></pre>
<h3 id="16-"><a href="https://leetcode-cn.com/problems/3sum-closest/">16. 最接近的三数之和</a></h3>
<p>给定一个包括 <em>n</em> 个整数的数组 <code>nums</code> 和 一个目标值 <code>target</code>。找出 <code>nums</code> 中的三个整数，使得它们的和与 <code>target</code> 最接近。返回这三个数的和。假定每组输入只存在唯一答案。</p>
<h4 id="-"><strong>示例：</strong></h4>
<pre><code>输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
</code></pre><hr>
<h4 id="-">解法</h4>
<p>思路：三指针</p>
<pre><code class="lang-java">class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length &lt; 3){
            return 0;
        }

        Arrays.sort(nums);
        int res = 0;
        int minAbs = Integer.MAX_VALUE;
        for(int i = 0;i &lt; nums.length; i ++){
            if(i &gt; 0 &amp;&amp; nums[i] == nums[i - 1]){
                continue;
            }
            //确定两个指针
            int left = i + 1;
            int right = nums.length - 1;
            while(left &lt; right){
                //当前和
                int cur = nums[i] + nums[left] + nums[right];
                //与目标差的绝对值
                int curAbs = Math.abs(target - cur);
                if(cur == target){
                    return cur;
                }
                //更新最小绝对值
                if(minAbs &gt; curAbs){
                    minAbs = curAbs;
                    res = cur;
                }
                if(cur &gt; target){
                    right--;
                    while(left &lt; right &amp;&amp; nums[right] == nums[right + 1]){
                        right--;
                    }
                }else{
                    left++;
                    while(left &lt; right &amp;&amp; nums[left] == nums[left - 1]){
                        left++;
                    }
                }
            }
        }
        return res;
    }
}
</code></pre>
<h3 id="18-"><a href="https://leetcode-cn.com/problems/4sum/">18. 四数之和</a></h3>
<p>给定一个包含 <em>n</em> 个整数的数组 <code>nums</code> 和一个目标值 <code>target</code>，判断 <code>nums</code> 中是否存在四个元素 <em>a，**b，c</em> 和 <em>d</em> ，使得 <em>a</em> + <em>b</em> + <em>c</em> + <em>d</em> 的值与 <code>target</code> 相等？找出所有满足条件且不重复的四元组。</p>
<p><strong>注意：</strong>答案中不可以包含重复的四元组。</p>
<h4 id="-1-"><strong>示例 1：</strong></h4>
<pre><code>输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
</code></pre><h4 id="-2-"><strong>示例 2：</strong></h4>
<pre><code>输入：nums = [], target = 0
输出：[]
</code></pre><hr>
<h4 id="-">解法</h4>
<p>思路：两层for 循环确定两个固定指针，在确定两个游动指针，进行移动是的四数之和向target靠近。</p>
<p>​           两层for，第一层for到倒数第四个数，第二层到倒数第三个数，留下至少两个数做游动指针。</p>
<pre><code class="lang-java">class Solution {
    public List&lt;List&lt;Integer&gt;&gt; fourSum(int[] nums, int target) {
       List&lt;List&lt;Integer&gt;&gt; quadruplets = new ArrayList&lt;List&lt;Integer&gt;&gt;();
        if (nums == null || nums.length &lt; 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        //第一层for到倒数第四个数
        for (int i = 0; i &lt; length - 3; i++) {
            if (i &gt; 0 &amp;&amp; nums[i] == nums[i - 1]) {
                continue;
            }
            //到此位置最小值都大于target，说明之后的不存在答案
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] &gt; target) {
                break;
            }
            //当前最大值都小于target，说明当前位置不可能
            if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] &lt; target) {
                continue;
            }
            //第二层到倒数第三个数
            for (int j = i + 1; j &lt; length - 2; j++) {
                if (j &gt; i + 1 &amp;&amp; nums[j] == nums[j - 1]) {
                    continue;
                }
                //到此位置最小值都大于target，说明之后的不存在答案
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] &gt; target) {
                    break;
                }
                //当前最大值都小于target，说明当前位置不可能
                if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] &lt; target) {
                    continue;
                }
                //确定两个游动指针
                int left = j + 1, right = length - 1;
                while (left &lt; right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        //重复的跳过
                        while (left &lt; right &amp;&amp; nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left &lt; right &amp;&amp; nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum &lt; target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}
</code></pre>

          	</article>
        </div>
		</div>
  </body>
</html>
<script type="text/javascript" src="toc/js/jquery-1.4.4.min.js"></script>
<script type="text/javascript" src="toc/js/jquery.ztree.all-3.5.min.js"></script>
<script type="text/javascript" src="toc/js/ztree_toc.js"></script>
<script type="text/javascript" src="toc_conf.js"></script>

<SCRIPT type="text/javascript" >
<!--
$(document).ready(function(){
    var css_conf = eval(markdown_panel_style);
    $('#readme').css(css_conf)
    
    var conf = eval(jquery_ztree_toc_opts);
		$('#tree').ztree_toc(conf);
});
//-->
</SCRIPT>